package visualizer.client.algorithms.sBst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

import java.util.ArrayList;
import java.util.List;

/**
 * User: DDovzhenko
 * Date: 07.01.14
 * Time: 18:26
 */
public class SBSTRemovingAlgorithm implements Algorithm {
    private BinaryTree tree;
    private List<AlgoResult> results = new ArrayList<AlgoResult>();
    boolean isRemoved;

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return results.get(step);
    }

    @Override
    public int getStepsCount(BinaryTree binaryTree, int inputValue) {
        results.clear();
        isRemoved = true;
        results.add(new AlgoResult(binaryTree.copyTree(false), " Удаление узла с ключом " + inputValue));
        tree = binaryTree.copyTree(false);
        tree.setRootNode(remove(tree.getRoot(), inputValue));
        results.add(new AlgoResult(tree, isRemoved ? "Узел успешно удален" : "Узел с таким ключом не существует, выполнен последнего посещенного узла к корню"));
        return results.size();
    }

    private BNode remove(BNode root, Integer value) {
        if (root == null) {
            isRemoved = false;
            return null;
        }

        results.add(new AlgoResult(tree.copyTree(true), "Ищем удаляемый узел и перемещаем его в корень"));
        boolean isFound = SplayBSTUtils.search(tree, value, results);
        if (isFound) {
            results.add(new AlgoResult(tree.copyTree(true), "Узел найден, переместим его в корень"));
        } else {
            results.add(new AlgoResult(tree.copyTree(true), "Узел не найден, переместим последний посещенный узел в корень"));
        }
        SplayBSTUtils.splay(tree, value, results);
        root = tree.getRoot();

        int cmp = value.compareTo(root.getValue());

        if (cmp == 0) {
            if (root.getLeftBNode() == null) {
                results.add(new AlgoResult(tree.copyTree(true), "У удаляемого узла нет левого поддерева, делаем правый дочерний узел корнем дерева"));
                return root.getRightBNode();
            } else {
                results.add(new AlgoResult(tree.copyTree(true), "Удаляем корень, оставляя левое и правое деревья"));
                int oldRootValue = root.getValue();
                BNode x = root.getRightBNode();
                root = root.getLeftBNode();
                tree.setRootNode(root);
                int size = results.size();
                results.add(new AlgoResult(tree.copyTree(true), "Найдем наибольший элемент в левом дереве"));
                SplayBSTUtils.search(tree, value, new ArrayList<AlgoResult>());
                results.add(new AlgoResult(tree.copyTree(true), "Теперь переместим его в корень"));
                SplayBSTUtils.splay(tree, value, results);
                for (int i = size; i < results.size(); i++) {
                    BinaryTree resTree = results.get(i).getTree();
                    updateTree(x, resTree, oldRootValue);
                }
                BinaryTree resTree = tree.copyTree(true);
                updateTree(x, resTree, oldRootValue);
                results.add(new AlgoResult(resTree, "Левое дерево теперь не имеет правого поддерева, объединим левое и правое деревья"));

                root = tree.getRoot();
                root.setRightBNode(x);
                return root;
            }
        }

        isRemoved = false;
        return root;
    }

    private void updateTree(BNode x, BinaryTree resTree, int oldRootValue) {
        BNode newRoot = new BNode(oldRootValue);
        newRoot.setVisible(false);
        newRoot.setLeftBNode(resTree.getRoot());
        newRoot.setRightBNode(x);
        resTree.setRootNode(newRoot);
    }
}
